package lcr;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Test0081 {
}

class Solution0081_1 {
    List<List<Integer>> ans = new ArrayList<>();
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        traceback(candidates,target,0,new ArrayList<>());
        return ans;
    }

    public void traceback(int[] candidates, int target,int index,List<Integer> list){
        if (target==0){
            ans.add(new ArrayList<>(list));
            return;
        }

        for (int i = index; i < candidates.length; i++) {
            if (target<candidates[i]) break;

            list.add(candidates[i]);
            traceback(candidates,target-candidates[i],i,list);
            list.remove(list.size()-1);
        }
    }
}
